package week01

// 1248. 统计「优美子数组」
// https://leetcode-cn.com/problems/count-number-of-nice-subarrays/

// 前缀和
// 子段和

// s[r] - s[l-1] == k  ->  ans++
// 固定r，内循环相当于计算 s[r]-k 的数量，即 s[l-1] 的数量
// 统计的是 sums[l-1] 的数量

func numberOfSubArrays(nums []int, k int) int {
	var n = len(nums)
	var sums = make([]int, n+1)
	var counts = make([]int, n+1)
	for i := 1; i <= n; i++ {
		sums[i] = sums[i-1] + nums[i-1] % 2
		counts[sums[i-1]] += 1
	}

	var ans = 0
	for i := 0; i <= n; i++ {
		if sums[i] - k >= 0 {
			ans += counts[sums[i]-k]
		}
	}
	return ans
}